数据结构 Tree 二叉查找树

参考资料二叉搜索树 LeetCode

二叉搜索树的定义

二叉搜索树（Binary Search Tree）是二叉树的一种特殊形式。二叉搜索树具有以下性质：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值。

二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

下面是一个二叉搜索树的例子：

像普通的二叉树一样，可以按照前序、中序和后序来遍历一个二叉搜索树。但是值得注意的是，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。因此，中序遍历是二叉搜索树中最常用的遍历方法。

测试工具

生成一颗二叉搜索树

/**
 * 生成一颗二叉搜索树
 */
public static TreeNode generateBSTree(int len) {
    int[] arr = new int[len];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i;
    }
    return buildBSTree(arr, 0, arr.length - 1);
}

/**
 * 构建二叉搜索树
 */
private static TreeNode buildBSTree(int[] nums, int lo, int hi) {
    if (lo > hi) {
        return null;
    }
    // 以升序数组的中间元素作为根节点 root。
    int mid = lo + (hi - lo) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    // 递归的构建 root 的左子树与右子树。
    root.left = buildBSTree(nums, lo, mid - 1);
    root.right = buildBSTree(nums, mid + 1, hi);
    return root;
}

使用：

TreeNode root = generateBSTree(14);

有序数组构建一颗二叉搜索树

/**
 * 生成一颗二叉搜索树（这里其实只是生成一个排序数组，核心是第二个方法）
 */
public static TreeNode generateBSTree(int len) {
    int[] arr = new int[len];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i;
    }
    return buildBSTree(arr, 0, arr.length -1);
}


/**
 * 构建二叉搜索树
 */
private static TreeNode buildBSTree(int[] nums, int lo, int hi) {
    if (lo > hi) {
        return null;
    }
    // 以升序数组的中间元素作为根节点 root。
    int mid = lo + (hi - lo) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    // 递归的构建 root 的左子树与右子树。
    root.left = buildBSTree(nums, lo, mid - 1);
    root.right = buildBSTree(nums, mid + 1, hi);
    return root;
}

验证二叉搜索树 ⭐

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

这题很简单，直接使用 中序遍历 就行，使用中序遍历可以发现它是逐步升序的，如果某个节点比之前那个小就不是二叉搜索树

使用递归的方式

/**
 * 判断是否为二叉搜索树
 */
public static boolean isBST(TreeNode head, int max) {
    if (head == null) return true;
    if (head.left != null) return isBST(head.left, max);
    if (head.value <= max) {
        return false;
    } else {
        max = head.value;
    }
    if (head.right != null) return isBST(head.right, max);
    return true;
}

使用：

System.out.println(isBST(root, Integer.MIN_VALUE));

使用迭代的方式

/**
 * 判断是否为二叉搜索树
 */
public static boolean isBST(TreeNode head) {
    if (head == null) return true;
    Stack<TreeNode> stack = new Stack<>();
    int max = Integer.MIN_VALUE;
    while (!stack.isEmpty() || head != null) {
        if (head != null) {
            stack.push(head);
            head = head.left;
        } else {
            head = stack.pop();
            // 这里判断大小
            if (head.value <= max) {
                return false;
            } else {
                max = head.value;
            }
            head = head.right;
        }
    }
    return true;
}

使用 DP 解（DP 法）⭐

参考左神的教程： 0:46:00

左树得是搜索二叉树
右树得是搜索二叉树
左树最大值小于 Root 节点的值
右树最小值大于 Root 节点的值

所以它向它的左树需要什么信息？

左树是否是搜索二叉树
然后左树的最大值

它向它的右树需要什么信息？

右树是否是搜索二叉树
右树的最小值

总结一下：整个判断只需用大下面三个信息：

最大值是什么？
最小值是什么？
是否是搜索二叉树？

算法如下：

    /**
     * 判断是否为二叉搜索树
     */
    public static boolean isBST(TreeNode head) {
        return process(head).isBST;
    }

    /**
     * 返回 Data 这里存了需要的三个信息
     */
    public static class ReturnData {
        boolean isBST;
        int max;
        int min;

        public ReturnData(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static ReturnData process(TreeNode x) {
        if (x == null) return null;
        // 这里其实就是拆黑盒的过程，不用管它怎么拿到的
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);

        // 返回的三个信息
        int min = x.value;
        int max = x.value;
        // 这里的 min 主要取得最小值
        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        // 这里的 max 主要取得最大值
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }

        boolean isBST = true;

        // 这里就是主要的判断条件
        if (leftData != null && (!leftData.isBST || leftData.max >= x.value)) isBST = false;
        if (rightData != null && (!rightData.isBST || rightData.min <= x.value)) isBST = false;

        // 把三个信息传递出去
        return new ReturnData(isBST, min, max);
    }

其实就是一种 DP（动态规划）的过程，把需要的结果传递出去

所以遇到需要从左树取信息，右树取信息的题目就可以使用这个方法来解

算法题

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）

输入：

[4,8,6,12,16,14,10]

返回值

true

解析：一颗二叉搜索树（就是二叉查找树），如下所示

后序遍历为：

[5,7,6,9,11,10,8]

由后序遍历，已经右数一定比 Root 大的特性，只需遍历这个数组，找到第一个比 8 大的下标，将其分成左右子树，按照这种方式，不断的递归。

如果遍历的过程中，先出现了大于根节点的节点，后面又出现了小于根节点的节点，则说明不是二叉搜索树的后序遍历序列。比如 [7,4,6,5] 这样的序列。

class Solution {
    // 要点：二叉搜索树中根节点的值大于左子树中的任何一个节点的值，小于右子树中任何一个节点的值，子树也是
    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length < 2) return true;
        return verify(postorder, 0, postorder.length - 1); 
    }

    // 递归实现
    private boolean verify(int[] postorder, int left, int right){
        if (left >= right) return true; // 当前区域不合法的时候直接返回true就好

        int rootValue = postorder[right]; // 当前树的根节点的值

        int k = left;
        while (k < right && postorder[k] < rootValue){ // 从当前区域找到第一个大于根节点的，说明后续区域数值都在右子树中
            k++;
        }

        for (int i = k; i < right; i++){ // 进行判断后续的区域是否所有的值都是大于当前的根节点，如果出现小于的值就直接返回false
            if (postorder[i] < rootValue) return false;
        }

        // 当前树没问题就检查左右子树
        if (!verify(postorder, left, k - 1)) return false; // 检查左子树

        if (!verify(postorder, k, right - 1)) return false; // 检查右子树

        return true; // 最终都没问题就返回true
    }
}

二叉搜索树的第k个结点

这题主要就是考察二叉搜索树的中序遍历就是排序后的队列，以及迭代的方式中序遍历

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    // 因为是二叉搜索树，所以就是中序遍历的顺序
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k == 0) return null;
        Stack<TreeNode> stack = new Stack<>();
        int count = 0;
        while (!stack.isEmpty() || pRoot != null) {
            while (pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            // 取得最左的第一个元素
            TreeNode node = stack.pop();
            if (++count == k) return node;
            // 指向右边的节点（就算为空也有 Stack 的内容）
            pRoot = node.right;
        }
        
        return null;
    }
}

二叉搜索树的定义​

测试工具​

有序数组构建一颗二叉搜索树​

验证二叉搜索树 ⭐​

使用递归的方式​

使用迭代的方式​

使用 DP 解（DP 法）⭐​

算法题​

二叉搜索树的后序遍历序列​

二叉搜索树的第k个结点​